{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This Python 3 environment comes with many helpful analytics libraries installed\n",
    "# It is defined by the kaggle/python docker image: https://github.com/kaggle/docker-python\n",
    "# For example, here's several helpful packages to load in \n",
    "\n",
    "import numpy as np # linear algebra\n",
    "import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n",
    "import math\n",
    "from collections import Counter\n",
    "\n",
    "# Input data files are available in the \"../input/\" directory.\n",
    "# For example, running this (by clicking run or pressing Shift+Enter) will list the files in the input directory\n",
    "\n",
    "from subprocess import check_output\n",
    "# print(check_output([\"ls\", \"../input\"]).decode(\"utf8\"))\n",
    "\n",
    "n_children = 1000000 # n children to give\n",
    "n_gift_type = 1000 # n types of gifts available\n",
    "n_gift_quantity = 1000 # each type of gifts are limited to this quantity\n",
    "n_gift_pref = 100 # number of gifts a child ranks\n",
    "n_child_pref = 1000 # number of children a gift ranks\n",
    "twins = math.ceil(0.04 * n_children / 2.) * 2    # 4% of all population, rounded to the closest number\n",
    "triplets = math.ceil(0.005 * n_children / 3.) * 3    # 0.5% of all population, rounded to the closest number\n",
    "ratio_gift_happiness = 2\n",
    "ratio_child_happiness = 2\n",
    "\n",
    "gift_pref = pd.read_csv('../input/child_wishlist_v2.csv',header=None).drop(0, 1).values\n",
    "child_pref = pd.read_csv('../input/gift_goodkids_v2.csv',header=None).drop(0, 1).values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((1000000, 100), (1000, 1000))"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gift_pref.shape, child_pref.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Child(object):   \n",
    "    def __init__(self, idx, prefer):   \n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()   \n",
    "        for i in range(prefer.shape[0]):\n",
    "            self.prefer_dict[prefer[i]] = [12*(prefer.shape[0] - i), -6]\n",
    "      \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        \n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 6*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 6*score]      \n",
    "        return None\n",
    "        \n",
    "    def happiness(self, giftid):  \n",
    "        return self.prefer_dict.get(giftid, [-6, -6])\n",
    "    \n",
    "class Child_twin(object):\n",
    "    def __init__(self, idx, prefer1, prefer2):\n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        for p in list(set(list(prefer1) + list(prefer2))):\n",
    "            score = 0\n",
    "            if p in list(prefer1):\n",
    "                score += 2*(100 - list(prefer1).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            if p in list(prefer2):\n",
    "                score += 2*(100 - list(prefer2).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            self.prefer_dict[p] = [3*score, -6]\n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 3*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 3*score]\n",
    "        return None\n",
    "        \n",
    "    def happiness(self, giftid):\n",
    "        return self.prefer_dict.get(giftid, [-6, -6])\n",
    "    \n",
    "class Child_triplet(object):\n",
    "    def __init__(self, idx, prefer1, prefer2, prefer3):\n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        for p in list(set(list(prefer1) + list(prefer2) + list(prefer3))):\n",
    "            score = 0\n",
    "            if p in list(prefer1):\n",
    "                score += 2*(100 - list(prefer1).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            if p in list(prefer2):\n",
    "                score += 2*(100 - list(prefer2).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            if p in list(prefer3):\n",
    "                score += 2*(100 - list(prefer3).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            self.prefer_dict[p] = [2*score, -6]\n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 2*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 2*score]\n",
    "        return None\n",
    "        \n",
    "    def happiness(self, giftid):\n",
    "        return self.prefer_dict.get(giftid, [-6, -6])\n",
    "    \n",
    "Children = []\n",
    "for i in range(0, 5001, 3):\n",
    "    Children.append(Child_triplet(i, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "    Children.append(Child_triplet(i+1, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "    Children.append(Child_triplet(i+2, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "for i in range(5001, 45001, 2):\n",
    "    Children.append(Child_twin(i, gift_pref[i], gift_pref[i+1]))\n",
    "    Children.append(Child_twin(i+1, gift_pref[i], gift_pref[i+1]))\n",
    "Children = Children + [Child(i, gift_pref[i]) for i in range(45001, 1000000)]\n",
    "\n",
    "for j in range(1000):\n",
    "    cf = child_pref[j]\n",
    "    done_list = []\n",
    "    for i in range(cf.shape[0]):\n",
    "        if cf[i] <= 5000 and cf[i] not in done_list:\n",
    "            if cf[i] % 3 == 0:\n",
    "                cid1 = cf[i]\n",
    "                cid2 = cf[i] + 1\n",
    "                cid3 = cf[i] + 2\n",
    "                done_list.append(cid2)\n",
    "                done_list.append(cid3)\n",
    "            elif cf[i] % 3 == 1:\n",
    "                cid1 = cf[i] - 1\n",
    "                cid2 = cf[i]\n",
    "                cid3 = cf[i] + 1\n",
    "                done_list.append(cid1)\n",
    "                done_list.append(cid3)\n",
    "            else:\n",
    "                cid1 = cf[i] - 2\n",
    "                cid2 = cf[i] - 1\n",
    "                cid3 = cf[i]\n",
    "                done_list.append(cid1)\n",
    "                done_list.append(cid2)\n",
    "            if cid1 in list(cf):\n",
    "                score_ = 2*(cf.shape[0] - list(cf).index(cid1))\n",
    "            else:\n",
    "                score_ = -1\n",
    "            if cid2 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid2))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            if cid3 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid3))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            Children[cid1].add_gifts_prefer(j, score_)\n",
    "            Children[cid2].add_gifts_prefer(j, score_)\n",
    "            Children[cid3].add_gifts_prefer(j, score_)\n",
    "        elif cf[i] <= 45000 and cf[i] not in done_list:\n",
    "            if cf[i] % 2 == 1:\n",
    "                cid1 = cf[i]\n",
    "                cid2 = cf[i] + 1\n",
    "                done_list.append(cid2)\n",
    "            else:\n",
    "                cid1 = cf[i] - 1\n",
    "                cid2 = cf[i]\n",
    "                done_list.append(cid1)\n",
    "            if cid1 in list(cf):\n",
    "                score_ = 2*(cf.shape[0] - list(cf).index(cid1))\n",
    "            else:\n",
    "                score_ = -1\n",
    "            if cid2 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid2))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            Children[cid1].add_gifts_prefer(j, score_)\n",
    "            Children[cid2].add_gifts_prefer(j, score_)\n",
    "        elif cf[i] > 45000:\n",
    "            Children[cf[i]].add_gifts_prefer(j, 2*(cf.shape[0] - i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from ortools.graph import pywrapgraph\n",
    "\n",
    "W_CHILD = 1\n",
    "W_GIFTS = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "assignment = [-1]*1000000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# try ignore this twins"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# well assigned twins and triplets\n",
    "well_assigned = [34267, 34268]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "101550505"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_cost_flow = pywrapgraph.SimpleMinCostFlow()\n",
    "\n",
    "start_nodes = []\n",
    "end_nodes = []\n",
    "capacities = []\n",
    "unit_costs = []\n",
    "\n",
    "# triplets\n",
    "for i in range(0, 5001, 3):\n",
    "    if i not in well_assigned:\n",
    "        for g in Children[i].prefer_dict.keys():\n",
    "            start_nodes.append(1000000+g)\n",
    "            end_nodes.append(i)\n",
    "            capacities.append(3)\n",
    "            unit_costs.append(1-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "            \n",
    "# twins\n",
    "for i in range(5001, 45001, 2):\n",
    "    if i not in well_assigned:\n",
    "        for g in Children[i].prefer_dict.keys():\n",
    "            start_nodes.append(1000000+g)\n",
    "            end_nodes.append(i)\n",
    "            capacities.append(2)\n",
    "            unit_costs.append(1-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "        \n",
    "# other children\n",
    "for i in range(45001, 1000000):\n",
    "    \n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(1)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "\n",
    "# 2.add Arc\n",
    "# gift -> children\n",
    "for i in range(len(start_nodes)):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(start_nodes[i]), int(end_nodes[i]), int(capacities[i]), int(unit_costs[i])\n",
    "    )\n",
    "    \n",
    "# children -> 1001000 : collection\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(3), int(0)\n",
    "    )\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(2), int(0)\n",
    "    )\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(1), int(0)\n",
    "    )\n",
    "    \n",
    "# gift -> 1001001 : dust_gift\n",
    "for i in range(1000):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(1000000+i), int(1001001), int(1000), int(0)\n",
    "    )\n",
    "    \n",
    "# 1001001 -> 1001000 : dust_path\n",
    "min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "    int(1001001), int(1001000), int(1000000), int(0)\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 3.add Supply\n",
    "for i in range(1000):\n",
    "    min_cost_flow.SetNodeSupply(int(1000000+i), int(1000))\n",
    "\n",
    "# children\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow.SetNodeSupply(int(i), int(0))\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow.SetNodeSupply(int(i), int(0))\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow.SetNodeSupply(int(i), int(0))\n",
    "\n",
    "min_cost_flow.SetNodeSupply(int(1001001), int(0)) \n",
    "min_cost_flow.SetNodeSupply(int(1001000), int(-1000000)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_cost_flow.Solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 0 11739596200 107346 1617929065388072772382660257736\n",
      "0.9363015424699496\n"
     ]
    }
   ],
   "source": [
    "# childID对giftID的配对关系\n",
    "assignment = [-1]*1000000\n",
    "twins_differ = []\n",
    "triplets_differ = []\n",
    "\n",
    "#for i in well_assigned:\n",
    "#    assignment[i] = assignment_0[i]\n",
    "\n",
    "for i in range(min_cost_flow.NumArcs()):\n",
    "    if min_cost_flow.Flow(i) != 0 and min_cost_flow.Head(i) < 1000000:\n",
    "        c = min_cost_flow.Head(i)\n",
    "        g = min_cost_flow.Tail(i)\n",
    "        f = min_cost_flow.Flow(i)\n",
    "\n",
    "        if c >= 45001:\n",
    "            assignment[c] = g - 1000000\n",
    "\n",
    "        elif c >= 5001:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    twins_differ.append([c, c+1])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "            elif f == 2:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "        else:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                elif assignment[c+1] == -1:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                else:\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 2:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 3:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "                assignment[c+2] = g - 1000000\n",
    "                \n",
    "CHILD_HAPPINESS = sum([Children[i].happiness(assignment[i])[0] for i in range(1000000)])*10\n",
    "SANTA_HAPPINESS = sum([Children[i].happiness(assignment[i])[1] for i in range(1000000)])\n",
    "OBJ = CHILD_HAPPINESS**3 + SANTA_HAPPINESS**3\n",
    "print(W_CHILD, W_GIFTS, CHILD_HAPPINESS, SANTA_HAPPINESS, OBJ)\n",
    "print(OBJ / (12000000000**3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 假设[34267,34268]已经满足要求，得到的CH为1173959620，\n",
    "- 下面遍历[34267]偏好列表中的礼物j，使得CH>=1173959620"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 34267, 34268 must be happy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# children\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow.SetNodeSupply(int(i), int(0))\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow.SetNodeSupply(int(i), int(0))\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow.SetNodeSupply(int(i), int(0))\n",
    "\n",
    "min_cost_flow.SetNodeSupply(int(1001001), int(0)) \n",
    "min_cost_flow.SetNodeSupply(int(1001000), int(-999998))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "j =  0\n",
      "j =  1\n",
      "j =  5\n",
      "j =  6\n",
      "j =  32\n",
      "j =  33\n",
      "j =  38\n",
      "j =  51\n",
      "j =  63\n",
      "j =  69\n",
      "j =  71\n",
      "j =  81\n",
      "j =  82\n",
      "j =  84\n",
      "j =  93\n",
      "j =  94\n",
      "j =  98\n",
      "j =  113\n",
      "j =  117\n",
      "j =  119\n",
      "j =  122\n",
      "j =  124\n",
      "j =  125\n",
      "j =  126\n",
      "j =  127\n",
      "j =  128\n",
      "j =  141\n",
      "j =  142\n",
      "j =  144\n",
      "j =  148\n",
      "j =  158\n",
      "j =  162\n",
      "j =  166\n",
      "j =  172\n",
      "j =  180\n",
      "j =  188\n",
      "j =  198\n",
      "j =  201\n",
      "j =  204\n",
      "j =  207\n",
      "1 0 11739596260 105303 1617929090195334238910239029127\n",
      "0.9363015568260036\n",
      "j =  211\n",
      "j =  212\n",
      "j =  213\n",
      "j =  223\n",
      "j =  224\n",
      "j =  232\n",
      "j =  246\n",
      "j =  248\n",
      "j =  256\n",
      "j =  257\n",
      "j =  261\n",
      "j =  267\n",
      "j =  273\n",
      "j =  280\n",
      "j =  285\n",
      "j =  289\n",
      "j =  290\n",
      "j =  291\n",
      "j =  293\n",
      "j =  296\n",
      "j =  299\n",
      "j =  301\n",
      "j =  311\n",
      "j =  317\n",
      "j =  321\n",
      "j =  322\n",
      "j =  326\n",
      "j =  329\n",
      "j =  331\n",
      "j =  333\n",
      "j =  338\n",
      "j =  347\n",
      "j =  382\n",
      "j =  384\n",
      "j =  392\n",
      "j =  402\n",
      "j =  403\n",
      "j =  404\n",
      "j =  418\n",
      "j =  425\n",
      "j =  426\n",
      "j =  428\n",
      "j =  436\n",
      "j =  438\n",
      "j =  448\n",
      "j =  463\n",
      "j =  464\n",
      "j =  468\n",
      "j =  469\n",
      "j =  471\n",
      "j =  474\n",
      "j =  491\n",
      "j =  492\n",
      "j =  497\n",
      "j =  500\n",
      "j =  512\n",
      "j =  517\n",
      "j =  521\n",
      "j =  528\n",
      "j =  542\n",
      "j =  543\n",
      "j =  549\n",
      "j =  557\n",
      "j =  562\n",
      "j =  564\n",
      "j =  575\n",
      "j =  577\n",
      "j =  579\n",
      "j =  581\n",
      "j =  582\n",
      "j =  608\n",
      "j =  620\n",
      "j =  628\n",
      "j =  637\n",
      "j =  638\n",
      "j =  644\n",
      "j =  658\n",
      "j =  659\n",
      "j =  661\n",
      "j =  665\n",
      "j =  667\n",
      "j =  668\n",
      "j =  674\n",
      "j =  675\n",
      "j =  690\n",
      "j =  691\n",
      "j =  693\n",
      "j =  695\n",
      "j =  697\n",
      "j =  699\n",
      "j =  700\n",
      "j =  708\n",
      "j =  712\n",
      "j =  721\n",
      "j =  722\n",
      "j =  724\n",
      "j =  728\n",
      "j =  731\n",
      "j =  734\n",
      "j =  746\n",
      "j =  751\n",
      "j =  753\n",
      "j =  754\n",
      "j =  755\n",
      "j =  759\n",
      "j =  764\n",
      "j =  773\n",
      "j =  780\n",
      "j =  781\n",
      "j =  790\n",
      "j =  791\n",
      "j =  794\n",
      "j =  803\n",
      "j =  810\n",
      "j =  818\n",
      "j =  823\n",
      "j =  824\n",
      "j =  825\n",
      "j =  829\n",
      "j =  831\n",
      "j =  833\n",
      "j =  850\n",
      "j =  851\n",
      "j =  854\n",
      "j =  855\n",
      "j =  862\n",
      "j =  869\n",
      "j =  872\n",
      "j =  876\n",
      "j =  879\n",
      "j =  887\n",
      "j =  911\n",
      "j =  912\n",
      "j =  914\n",
      "j =  928\n",
      "j =  931\n",
      "j =  940\n",
      "j =  941\n",
      "j =  963\n",
      "j =  971\n",
      "j =  972\n",
      "j =  979\n",
      "j =  984\n",
      "j =  988\n",
      "j =  992\n"
     ]
    }
   ],
   "source": [
    "# 将礼物j手动分发给双胞胎\n",
    "for j in range(1000):\n",
    "    # 礼物j是否在[34267]的编号列表中\n",
    "    if Children[34267].happiness(j)[0] > 0:\n",
    "        # 如果礼物j在双胞胎的偏好列表中，将礼物j分发给twins，将礼物的supply设为998\n",
    "        min_cost_flow.SetNodeSupply(int(1000000+j), int(998))\n",
    "        print(\"j = \", j)\n",
    "        if min_cost_flow.Solve() == 1:\n",
    "            assignment = [-1]*1000000\n",
    "            twins_differ = []\n",
    "            triplets_differ = []\n",
    "\n",
    "            assignment[34267] = j\n",
    "            assignment[34268] = j\n",
    "            # 遍历所有通路\n",
    "            for i in range(min_cost_flow.NumArcs()):\n",
    "                # 取出所有在偏好列表中的通路\n",
    "                if min_cost_flow.Flow(i) != 0 and min_cost_flow.Head(i) < 1000000:\n",
    "                    c = min_cost_flow.Head(i)# child\n",
    "                    g = min_cost_flow.Tail(i)# gift\n",
    "                    f = min_cost_flow.Flow(i)# flow\n",
    "\n",
    "                    if c >= 45001:\n",
    "                        assignment[c] = g - 1000000\n",
    "\n",
    "                    elif c >= 5001:\n",
    "                        # 若通路只有一个礼物，\n",
    "                        if f == 1:\n",
    "                            # 若当前孩子还没有礼物，将礼物给当前孩子，标记当前twins为拥有不同礼物的twins\n",
    "                            # 建立网络通路的时候，礼物只与twins的第一个节点建立通路\n",
    "                            if assignment[c] == -1:\n",
    "                                assignment[c] = g - 1000000\n",
    "                                twins_differ.append([c, c+1])\n",
    "                            # 若当前孩子已经有礼物，将礼物给他的兄弟（为什么不用标记？）\n",
    "                            else:\n",
    "                                assignment[c+1] = g - 1000000\n",
    "                        # 若通路有两个礼物，将礼物给twins\n",
    "                        elif f == 2:\n",
    "                            assignment[c] = g - 1000000\n",
    "                            assignment[c+1] = g - 1000000\n",
    "                    else:\n",
    "                        # 若通路只有一个礼物\n",
    "                        if f == 1:\n",
    "                            # 若当前孩子没有礼物，将礼物给当前孩子，标记当前三胞胎为拥有不同礼物的三胞胎\n",
    "                            if assignment[c] == -1:\n",
    "                                assignment[c] = g - 1000000\n",
    "                                triplets_differ.append([c, c+1, c+2])\n",
    "                            # 若当前孩子有礼物，2号孩子没有礼物，就给2号孩子（为什么不用标记）\n",
    "                            elif assignment[c+1] == -1:\n",
    "                                assignment[c+1] = g - 1000000\n",
    "                            # 否则给3号孩子（为什么不用标记？）\n",
    "                            else:\n",
    "                                assignment[c+2] = g - 1000000\n",
    "                        # 若通路只有两个礼物\n",
    "                        elif f == 2:\n",
    "                            # 若当前孩子没有礼物，将礼物给1、2号孩子，标记\n",
    "                            if assignment[c] == -1:\n",
    "                                assignment[c] = g - 1000000\n",
    "                                assignment[c+1] = g - 1000000\n",
    "                                triplets_differ.append([c, c+1, c+2])\n",
    "                            # 否则将礼物给2、3号孩子\n",
    "                            else:\n",
    "                                assignment[c+1] = g - 1000000\n",
    "                                assignment[c+2] = g - 1000000\n",
    "                        # 若通道有三个礼物，皆大欢喜\n",
    "                        elif f == 3:\n",
    "                            assignment[c] = g - 1000000\n",
    "                            assignment[c+1] = g - 1000000\n",
    "                            assignment[c+2] = g - 1000000\n",
    "            \n",
    "            CHILD_HAPPINESS = sum([Children[i].happiness(assignment[i])[0] for i in range(1000000)])*10\n",
    "            SANTA_HAPPINESS = sum([Children[i].happiness(assignment[i])[1] for i in range(1000000)])\n",
    "            OBJ = CHILD_HAPPINESS**3 + SANTA_HAPPINESS**3\n",
    "            # 验证把礼物j给[34267,34268]的情况下，CH能否满足要求\n",
    "            if CHILD_HAPPINESS >= 11739596220:\n",
    "                print(W_CHILD, W_GIFTS, CHILD_HAPPINESS, SANTA_HAPPINESS, OBJ)\n",
    "                print(OBJ / (12000000000**3))\n",
    "        else:\n",
    "            print(\"Failed to Solve!\")\n",
    "        min_cost_flow.SetNodeSupply(int(1000000+j), int(1000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
